package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-09 14:37
 */
public class AA34 {

    public static void main(String[] args) {
        int[] nums = {2,2};
        int[] index = searchRange(nums, 2);

        for (int i = 0; i < index.length; i++) {
            System.out.println(index[i]);
        }
    }


    public static int[] searchRange(int[] nums, int target) {
        int[] indexArray = {-1, -1};
        if (nums.length == 0) {
            return indexArray;
        }
        //二分法
        int index = binarySearch(nums, target, 0, nums.length - 1);
        if (index == -1) {
            return indexArray;
        }
        int start = index;
        int end = index;

        Boolean flag = true;
        while (flag){
            flag = false;
            if (start - 1 >= 0 && nums[start - 1] == target) {
                start--;
                flag = true;
            }
            if (end + 1 < nums.length && nums[end + 1] == target) {
                end++;
                flag = true;
            }
        }
        indexArray[0] = start;
        indexArray[1] = end;
        return indexArray;
    }

    public static int binarySearch(int[] nums, int target, int start, int end) {
        //二分查找
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else if (end - start <= 1) {
            return -1;
        }

        int index = (start + end + 1) / 2;
        if (target == nums[index]) {
            return index;
        }
        if (target > nums[index]) {
            return binarySearch(nums, target, index+1, end);
        } else {
            return binarySearch(nums, target, start, index-1);
        }
    }
}
